// @before-stub-for-debug-begin
#include <vector>
#include <string>


using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=332 lang=cpp
 *
 * [332] 重新安排行程
 *
 * https://leetcode-cn.com/problems/reconstruct-itinerary/description/
 *
 * algorithms
 * Hard (45.54%)
 * Likes:    537
 * Dislikes: 0
 * Total Accepted:    50.6K
 * Total Submissions: 110.7K
 * Testcase Example:  '[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]'
 *
 * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi]
 * 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 *
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK
 * 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
 *
 *
 * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
 *
 *
 * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
 * 输出：["JFK","MUC","LHR","SFO","SJC"]
 *
 *
 * 示例 2：
 *
 *
 * 输入：tickets =
 * [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
 * 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
 * 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1
 * tickets[i].length == 2
 * fromi.length == 3
 * toi.length == 3
 * fromi 和 toi 由大写英文字母组成
 * fromi != toi
 *
 *
 */

// @lc code=start
#include <unordered_map>
#include <set>
#include <vector>
#include<stack>
#include<algorithm>
#include <iostream>
using namespace std;
/* class Solution
{
public:
    vector<string> findItinerary(vector<vector<string>> &tickets)
    {
        unordered_multimap<string, string> hash;
        unordered_map<string, int> amount;
        vector<string> ans;
        ans.push_back("JFK");
        string source("JFK");
        string destiny;
        string finaldest;
        for (int i = 0; i < tickets.size(); ++i)
        {
            hash.insert({tickets[i][0], tickets[i][1]});
            ++amount[tickets[i][0]];
            ++amount[tickets[i][1]];
        }
        for (auto item : amount)
        {
            if (item.second % 2 != 0 && item.first != "JFK")
            {
                finaldest = item.first;
            }
        }
        while (!hash.empty())
        {
            auto cnt = hash.count(source);
            auto iter = hash.find(source);
            auto erase_iter = iter;
            destiny = iter->second;
            while (cnt)
            {
                if (hash.size() > 1)
                {
                    if (iter->second < destiny && hash.count(iter->second)&&iter->second!=finaldest)
                    {
                        erase_iter = iter;
                        destiny = iter->second;
                    }
                }
                else{
                    if (iter->second < destiny && hash.count(iter->second))
                    {
                        erase_iter = iter;
                        destiny = iter->second;
                    }
                }
                --cnt;
                ++iter;
            }
            ans.push_back(destiny);
            source = destiny;
            hash.erase(erase_iter);
        }
        return ans;
    }
}; */

class Solution
{
public:
    vector<string> findItinerary(vector<vector<string>> &tickets)
    {
        vector<string> ans;
        if(tickets.empty()){
            return ans;
        }
        unordered_map<string,multiset<string>> hash;
        // 存储每张票的出发地和目的地信息
        for(auto ticket:tickets){
            hash[ticket[0]].insert(ticket[1]);
        }
        stack<string> s;
        s.push("JFK");
        while(!s.empty()){
            string next=s.top();
            // 此时next对应的出发地已经没有机票，需要把next弹出，放入ans
            if(hash[next].empty()){
                ans.push_back(next);
                s.pop();
            }
            else{
                s.push(*hash[next].begin());
                hash[next].erase(hash[next].begin());
            }
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};
// @lc code=end
